package leetcode;

import java.util.Stack;

public class Code42 {

    public static void main(String[] args) {

    }
    public int trap2(int[] height) {
        if (height.length == 0) {
            return 0;
        }
        Stack<Item> items = new Stack<>();
        Stack<Water> waters = new Stack<>();
        int[] heightSum = new int[height.length];

        heightSum[0] = height[0];

        for (int a = 1; a < height.length; a++) {
            heightSum[a] = height[a] + heightSum[a - 1];
        }

        Water water = null;

        for (int a = 0; a < height.length; a++) {
            Item backLeft = null;
            while (!items.empty() && items.peek().getItemHeight() < height[a]) {
                backLeft = items.pop();
            }
            Item left = items.empty() ? backLeft : items.peek();
            if (left != null) {
                int maxWaterNum = Math.min(left.itemHeight, height[a]) * (a - 1 - left.getItemIndex()) - (heightSum[a - 1] - heightSum[left.getItemIndex()]);
                if (maxWaterNum != 0) {
                    water = new Water(left.getItemIndex(), a, maxWaterNum);
                }
            }

            items.push(new Item(height[a], a));

            if (water != null) {
                while (!waters.empty() && waters.peek().getStart() >= water.getStart()) {
                    waters.pop();
                }
                waters.push(water);
                water = null;
            }
        }

        int max = 0;
        while (!waters.empty()) {
            max += waters.pop().getWaterNumber();
        }
        return max;
    }

    class Item {
        private int itemHeight;
        private int itemIndex;

        public Item() {
            super();
        }

        public Item(int heigth, int itemIndex) {
            this.itemHeight = heigth;
            this.itemIndex = itemIndex;
        }

        public int getItemHeight() {
            return itemHeight;
        }

        public void setItemHeight(int itemHeight) {
            this.itemHeight = itemHeight;
        }

        public int getItemIndex() {
            return itemIndex;
        }

        public void setItemIndex(int itemIndex) {
            this.itemIndex = itemIndex;
        }
    }

    class Water {
        private int start;
        private int end;
        private int WaterNumber;

        public Water() {
            super();
        }

        public Water(int start, int end, int waterNumber) {
            this.start = start;
            this.end = end;
            this.WaterNumber = waterNumber;
        }

        public int getStart() {
            return start;
        }

        public void setStart(int start) {
            this.start = start;
        }

        public int getEnd() {
            return end;
        }

        public void setEnd(int end) {
            this.end = end;
        }

        public int getWaterNumber() {
            return WaterNumber;
        }

        public void setWaterNumber(int waterNumber) {
            WaterNumber = waterNumber;
        }
    }
}
